New Mexico được đặt lườn vào ngày 14 tháng 10 năm 1915 tại Xưởng hải quân New York; được hạ thủy vào ngày 13 tháng 4 năm 1917; được đỡ đầu bởi Cô Margaret Cabeza De Baca, con gái cựu Thống đốc tiểu bang New Mexico Ezequiel Cabeza De Baca (ông qua đời ngày 28 tháng 2 năm 1917); và được đưa vào hoạt động ngày 20 tháng 5 năm 1918 dưới quyền chỉ huy của Thuyền trưởng, Đại tá Hải quân Ashley Herman Robertson.

General Electric đã thực hiện một chiến dịch quảng cáo với tiêu đề "The "Constitution" of To-day—Electronically Propelled" (Chiếc "Constitution" của ngày hôm nay – vận hành bằng điện), bằng một hình vẽ chiếc New Mexico bên cạnh chiếc USS Constitution, và giới thiệu chiếc thiết giáp hạm mới như "chiếc tàu chiến đầu tiên thuộc mọi quốc gia vận hành bằng điện". Máy phát điện được cho biết có công suất 28.000 mã lực cung cấp động năng đạt được tốc độ đường trường 10 knot. GE gọi nó là một trong những tiến bộ hàng đầu của kỷ nguyên khoa học và liên hệ nó với những sản phẩm dân dụng, với chú thích rằng "Các ứng dụng tổng quát về điện năng được áp dụng để thỏa mãn nhu cầu của nhân loại tới mức ngày nay hiếm có một ngôi nhà hay một cá nhân nào không hưởng được lợi ích mà sản phẩm hay dịch vụ của General Electric mang lại". Một quyển sách nhỏ minh họa có tiêu đề "The Electric Ship" cũng được cung cấp miễn phí theo yêu cầu.[2]